from RandomList import GetRandomList
def dual_pivot_quick_sort(arr, low, high):
    if low < high: # 双基准点Pivots的快排
        lp, rp = partition(arr, low, high)
        dual_pivot_quick_sort(arr, low, lp - 1)
        dual_pivot_quick_sort(arr, lp + 1, rp - 1)
        dual_pivot_quick_sort(arr, rp + 1, high)
    
def partition(arr, low, high):
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    j = k = low + 1
    g, p, q = high - 1, arr[low], arr[high]
    while k <= g:
        if arr[k] < p:
            arr[k], arr[j] = arr[j], arr[k]
            j += 1

        elif arr[k] >= q:
            while arr[g] > q and k < g:
                g -= 1                 
            arr[k], arr[g] = arr[g], arr[k]
            g -= 1
            if arr[k] < p:
                arr[k], arr[j] = arr[j], arr[k]
                j += 1
        k += 1
    j -= 1
    g += 1
    arr[low], arr[j] = arr[j], arr[low]
    arr[high], arr[g] = arr[g], arr[high]
    return j, g


if __name__ == "__main__":
    Arr = GetRandomList(100)
    # dual_pivot_quick_sort(Arr, 0, len(Arr) - 1)
    # print(Arr)
    Arr = GetRandomList(7000)
    print("Max Heap Sort Running Time is " + str(round(timeit.timeit(lambda :dual_pivot_quick_sort(Arr, 0 ,len(Arr) - 1), number = 1) * 1000, 3 )) + " ms")

